package top.hudk.sort;

import java.util.Arrays;

/**
 * 功能或业务描述：希尔排序
 * 创建时间：2021/6/18 11:04
 * 作者：hudk
 */
public class ShellSort {


    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        //int[] array = {0,0,0,3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        int[] array = {44,2};
        shellSort.sort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 希尔排序
     * 基于插入排序的优化而来
     * @param arr
     */
    public void sort(int[] arr){
        if (arr == null || arr.length <= 1) {
            return;
        }
        int length  = arr.length;

        int step = length / 2;

        while (step > 0){
            //指定步长的插入排序
            insertionSort(arr, step);
            step /= 2;
        }

    }


    /**
     * 指定步长的插入排序
     * @param array
     * @param step
     */
    public void insertionSort(int[] array, int step) {
        if (array == null || array.length <= 1) {
            return;
        }
        int length = array.length;
        if(step < 0 || step > length/2){
            return;
        }
        // 要插入的数
        int insertNum;

        for (int i = step; i < length; i+=step) {
            insertNum = array[i];
            // 已经排序好的元素个数
            int j = i - step;
            while (j >= 0 && array[j] > insertNum) {
                // 从后到前循环，将大于insertNum的数向后移动一格
                array[j + step] = array[j];
                j -= step;
            }

            // 将需要插入的数放在要插入的位置
            array[j + step] = insertNum;
        }
    }

}
